package com.leetcode;

import java.util.ArrayList;
import java.util.List;

public class Leetcode235 {

    /* solution  1
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> leftList = getPath(root, p);
        List<TreeNode> rightList = getPath(root, q);
        TreeNode ancestor = null;
        for (int i = 0; i < leftList.size() && i < rightList.size(); i++) {
            if (leftList.get(i).equals(rightList.get(i))) {
                ancestor = leftList.get(i);
            } else {
                break;
            }
        }

        return ancestor;
    }

    private List<TreeNode> getPath(TreeNode root, TreeNode target) {
        List<TreeNode> pathNodes = new ArrayList<TreeNode>();
        TreeNode curr = root;

        while ((curr != null) && (curr != target)) {
            pathNodes.add(curr);
            if (target.val < curr.val) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }

        //target本身也需要加入到节点路径中
        pathNodes.add(curr);
        return pathNodes;
    }
*/
    /* solution  2
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==p||root==q||root==null){
            return root;
        }
        TreeNode left=null;
        TreeNode right=null;
        //根据二叉搜索树的性质选择

        //if(root.val>p.val||root.val>q.val),优化作用，不影响功能
        //二叉树遍历,直到返回p，q中的其中一个，如果是null，代表q，q都不在左树
        left=lowestCommonAncestor(root.left,p,q);
        //if(root.val<p.val||root.val<q.val),优化作用，不影响功能
        //二叉树遍历,直到返回p，q中的其中一个，如果是null，代表q，q都不在右树
        right=lowestCommonAncestor(root.right,p,q);

        //p,q，分别在当前节点的左右子树
        if(left!=null&&right!=null){
            return root;
        }

        //left是null，代表公共节点在右子树中
        if(left==null){
            return right;
        }else{
            return left;
        }
    }
    */

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode curr = root;
        while(true){
            if(p.val > curr.val && q.val>curr.val){
                curr = curr.right;
            }else if(p.val < curr.val && q.val < curr.val){
                curr = curr.left;
            }else{
                break;
            }
        }
        return curr;
    }

    public static void main(String[] args) {
        Leetcode235 leetcode235 = new Leetcode235();

        TreeNode root = new TreeNode(5);
        TreeNode left = new TreeNode(3);
        TreeNode right = new TreeNode(6);
        root.left = left;
        root.right = right;

        TreeNode result = leetcode235.lowestCommonAncestor(root, left, right);
        System.out.println(result.val);
    }
}
